#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<cstdio>

using namespace std;

int main()
{
    int n, x;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        bool z = true;
        cin >> x;
        if (x == 1) z = false;
        for (int j = 2; j * j <= x; j++)
        {
            if (x % j == 0)
            {
                z = false;
                printf("%d is not prime\n", x);
                break;
            }
        }
        if (z)
            printf("%d is prime\n", x);
    }
    return 0;
}
